package exer;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author tongchen
 * @create 2022-11-12 13:38
 */
public class SortReview {
    public static void main(String[] args) {
        int[]arr={9,8,7,6,4,5,3,2,1};//5655????
       // quickSort(arr,0, arr.length-1);
        //bubbleSort(arr);
       // heapSort(arr);
        //
        // selectSort(arr);
        //selectSortDouble(arr);
        //insertSort(arr);
        //shellSort(arr);
        //quickSortItr(arr);
        bubbleSort2(arr);
        System.out.println(Arrays.toString(arr));
    }

    //1.冒泡排序及其优化
    public static void bubbleSort(int[] arr) {
        //循环处理每个数字
        for (int i = 0; i < arr.length - 1; ++i) {
            //定义标识符
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            if (flag == false) {
                break;
            }
        }
    }

    //2.选择排序
    public static void selectSort(int[]arr){
        //把每个下标的值都作为最小值，不断进行最小值的调整
        for(int i=0;i< arr.length-1;++i){
            //共n个元素，需要调整n-1次
            int minIndex=i;
            int findMinIndex=findMinIndex(arr,i, arr.length);
            //交换查找相对（从当前元素到最后一个元素）最小值
            if(minIndex!=findMinIndex){
                swap(arr,minIndex,findMinIndex);
            }
        }

    }
    //2.2双指针选择排序
    public static void selectSortDouble(int[]arr){
        //定义双指针，确定指针终止条件
        int begin=0;
        int end= arr.length-1;
        while(begin<end){
            int minIndex=findMinIndex(arr,begin,end+1);
            int maxIndex=findMaxIndex(arr,begin,end+1);
            if(minIndex!=begin){
                swap(arr,begin,minIndex);
            }
            if(maxIndex!=end){
                if(maxIndex==begin){
                    maxIndex=minIndex;
                }
                swap(arr,end,maxIndex);
            }
            begin++;
            end--;
        }
    }

    private static int findMaxIndex(int[] arr, int begin, int end) {
        int maxIndex=begin;
        for(int i=begin;i<end;++i){
            if(arr[i]>arr[maxIndex]){
                maxIndex=i;
            }
        }
        return maxIndex;
    }

    private static int findMinIndex(int[] arr, int begin,int end) {
        //不断遍历查找最小值
        int minIndex=begin;
        for(int i=begin;i< end;++i){
            if(arr[i]<arr[minIndex]){
                minIndex=i;
            }
        }
        return minIndex;
    }

    //3.插入排序:主要思想是把前个数在有序的情况下将第n+1个数放在合适的位置
    public static void insertSort(int[]arr){
        //第一个数有序，从下标为1的位置开始排序
        for (int i = 1; i < arr.length ; i++) {
            //先将要排序的数保存起来
            int temp=arr[i];
            int j=i-1;
            while (j>=0){
                //将要排序的元素与从0-j的元素进行比较
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                    j--;
                }
                else{
                    break;
                }
            }
            arr[j+1]=temp;
        }

    }
    //4.希尔排序:希尔排序思想就是在插入排序的基础上，对数组进行规律性的分组
    public static void shellSort(int[]arr){
        //求分组数，并根据不同的分组进行排序
        int gap= arr.length/2;
        while(gap>=1){
            //在每一次分组后，将不同分组的子数组分别进行排序
            shellCore(arr,gap);
            gap/=2;
        }

    }

    private static void shellCore(int[] arr, int gap) {
        for(int i=gap;i<arr.length;i+=gap){
            //将当前值储存起来
            int temp=arr[i];
            //定义当前子数组前面的元素
            int j=i-gap;
            while(j>=0){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                    j-=gap;
                }
                else{
                    break;
                }
            }
            //将当前值放在合适的位置
            arr[j+gap]=temp;

        }
    }

    //5.堆排序
    public static void heapSort(int[] arr) {
        //1.创建堆
        createHeap(arr);
        //2.进行堆排序
        //定义末尾节点
        int end = arr.length - 1;
        while (end > 0) {
            //交换父子节点
            swap(arr, 0, end);
            //不断向下进行创建堆
            shiftDown(arr, 0, end);
            //end进行递减
            end--;
        }


    }

    private static void createHeap(int[] arr) {
        //找到最后一个父节点
        int parent = (arr.length - 1 - 1) / 2;
        for (int i = parent; i >= 0; --i) {
            shiftDown(arr, parent, arr.length);
        }

    }
    //冒泡排序2（一样的）
    public static void bubbleSort2(int[]arr){
        for(int i=0;i<arr.length-1;++i){
            //设置标志符
            boolean flag=false;
            for(int j=0;j< arr.length-1-i;++j){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
            if(flag==false){
                break;
            }
        }
    }

    private static void shiftDown(int[] arr, int parent, int end) {
        int child = (2 * parent + 1);
        //不断向下进行创建堆
        while (child < end) {
            //找到子节点中最大的值
            if (child + 1 < end) {
                if (arr[child] < arr[child + 1]) {
                    child++;
                }
            }
            //父子节点进行比较交换
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
            }
            //父子节点不断向下进行遍历
            parent = child;
            child = (2 * parent) + 1;
        }
    }

    //6.快速排序
    //快速排序的迭代实现
    public static void quickSortItr(int[]arr){
        //定义左右界限
        int left=0;
        int right= arr.length-1;
        //定义辅助栈
        Stack<Integer>stack=new Stack<>();
        //将左右结点入栈
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            int len = quickCore(arr, left, right);
            if(len-1>left){
                stack.push(left);
                stack.push(len-1);
            }
            if(right>len+1){
                stack.push(len+1);
                stack.push(right);
            }
        }

    }
    public static void quickSort(int[] arr, int left, int right) {
        //对指针的合法性进行校验
        if (left >= right) {
            return;
        }
        //int len = quickCore(arr, left, right);
        int len = quickSortDig(arr, left, right);
        //对左右两侧分别进行快排
        quickSort(arr, left, len - 1);
        quickSort(arr, len + 1, right);

    }

    private static int quickCore(int[] arr, int left, int right) {
        //将基准值进行储存
        int standardIndex = left;
        int standard = arr[left];
        //左右指针向对方走
        while (left < right) {
            while (right > left && arr[right] >= standard) {
                right--;
            }
            while (right > left && arr[left] <= standard) {
                left++;
            }
            //进行交换
            swap(arr, left, right);
        }
        //将基准值和左右指针重合点进行交换
        swap(arr, standardIndex, left);
        return left;

    }
    //快排的核心2(挖坑法)
    public static int quickSortDig(int[]arr,int left,int right){
        //储存基准值
        int standard=arr[left];
        //左右指针向彼此方向进行遍历
        while(left<right){
            while(left<right){
                while(left<right&&arr[right]>=standard){
                    right--;
                }
                //将右指针对应的值放入左指针部分
                arr[left]=arr[right];
                while(left<right&&arr[left]<=standard){
                    left++;
                }
                //将左指针对应的值放入右指针
                arr[right]=arr[left];
            }
        }
        //最后将基准值放入左右指针的下标
        arr[left]=standard;
        return left;

    }


    private static void swap(int[] arr, int j, int i) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

}
